package com.dy.字符串.实现strStr;
/*
实现strStr()
实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 */
public class Solution {
    public static int strStr(String haystack, String needle) {
        if(needle.equals("")) return 0;
        if(haystack.length()<needle.length()) return -1;
        if(needle.length()==1) return haystack.indexOf(needle.charAt(0));
        int index = -1;
        int h = haystack.length();
        int n = needle.length();
        for(int i =0 ;i<=h-n;i++){
            int j;
            for(j =0;j<n;j++){
                if(haystack.charAt(i+j)!=needle.charAt(j)){
                    break;
                }
            }
            if(j==n){
                return i;
            }
        }
        return -1;
    }
    //KMP
    /*
    使用部分匹配表，
    字符串前后缀 前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
    最长公有前后缀的长度即为部分匹配表的值
    前进已匹配长度-匹配表值
     */
    public static int strStr2(String haystack, String needle) {
        int next[] = getNext(needle);
        int i=0,j=0;
        while(i<haystack.length() && j<needle.length()){
            if(j==-1 || haystack.charAt(i)==needle.charAt(j)){ //j==-1时，表示haystack[i]!=needle[0],即第一个字母二者都不同，故++
                i++;j++;
            }
            else {
                j = next[j];
            }
        }
        if(j<needle.length()){
            return -1;
        }
        else{
            return i-needle.length();
        }

    }
    public static int[] getNext(String pattern){
        int next[]=new int[pattern.length()];
        next[0] = -1;
        next[1] = 0;
        int len=0;
        int j =1;
        while(j<pattern.length()-1){
            if(pattern.charAt(j)==pattern.charAt(len)){
                j++;
                len++;
                next[j] = len;
            }
            else{
                if(len==0){
                    next[++j]=0;
                }
                else
                {len = next[len];}
            }

        }
        return next;

    }
}
